package linkedtoqueue;

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * 使用双向链表模拟队列
 * 采用头插法 + 尾删法的方式
 */
@SuppressWarnings({"all"})
public class LinkedQueue {
    private Node head; // 头指针

    private Node last; // 始终指向链表的最后一个节点

    class Node{
        public int data;
        public Node pre; // 指向前一个节点
        public Node next; // 指向后面一个节点

        public Node(int data){
            this.data = data;
        }
    }

    // 入队
    public void offer(int data){
        addFirst(data);
    }

    // 出队
    public int poll(){
        return removeLast();
    }

    // 获取队头元素
    public int peek(){
        return last == null ? null : last.data; // 如果为head为空会报空指针异常 也可以自己处理 或者打印信息
    }

    //头插法
    public void addFirst(int data){
        Node newNode = new Node(data);
        // 如果head为空，即是第一个节点
        if (head == null){
            head = newNode;
            last = newNode;
            return;
        }
        // 正常的头插法
        newNode.next = head;
        head.pre = newNode;
        head = newNode;
    }

    // 头删法
    public int removeLast(){
        // 如果为空
        if (head == null){
            throw new RuntimeException("当前为空，无法出队");
        }
        // 如果仅剩下一个节点
        if (last == head){
            int val = last.data;
            head = null;
            last = null;
            return val;
        }
        // 尾部删除
        int val = last.data;
        last = last.pre;
        return val;
    }

    //得到队列的长度
    public int size(){
        int len = 0;
        Node cur = head;
        while (cur != null){
            len++;
            cur = cur.next;
        }
        return len;
    }


    // 清空队列
    public void clear(){
        Node cur = head;
        while (cur != null){
            Node curNext = cur.next;
            cur.pre = null;
            cur.next = null;
            cur = curNext;
        }
        head = null;
        last = null;
    }
}
